﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


//144
public class Solution95
{
    //递归法
    public IList<int> InorderTraversal1(TreeNode root)
    {

        IList<int> res = new List<int>();

        //先序遍历中左右
        Bianli(root, res);
        return res;


    }

    public void Bianli(TreeNode root, IList<int> res)
    {
        if (root == null)
        {
            return;
        }
        Console.WriteLine("当前节点：" + root.val);
        res.Add(root.val);
        Bianli(root.left, res);
        Bianli(root.right, res);
        //递归的终止条件
    }

    //迭代法，中序遍历左中右
    public IList<int> InorderTraversal(TreeNode root)
    {

        IList<int> res = new List<int>();

        //中序遍历左中右

        Stack<TreeNode> q = new Stack<TreeNode>();
        if (root == null)
        {
            return res;
        }
        TreeNode node = root;
        TreeNode pre = node;
        while (node != null | q.Count > 0)//q为空
        {

            while (node != null)//找到最左下角
            {

                q.Push(node);

                node = node.left;
            }

                node = q.Pop();//返回父亲节点
              

            if(node.right != null&& node.right!=pre)
            {
                q.Push(node);//再次入栈，再次出站的时候要判断一下了
                node = node.right;//开始遍历右边的
            }
            else//右子树空才可以输出
            {
                res.Add(node.val);//出栈的同时也加入数组，先序的关键
                pre = node;//记录上一个节点 
                node = null;//node.right==null,所以直接null
            }

                
            
           
        }


        return res;


    }


}
class Program95
{

    static void Main95(string[] args)
    {

        // 创建二叉树示例
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);

        // 创建 Solution 实例并调用 InorderTraversal 方法
        Solution95 solution = new Solution95();
        IList<int> result = solution.InorderTraversal(root);
        // 打印遍历结果
        Console.WriteLine("中序遍历结果：");
        foreach (int num in result)
        {
            Console.WriteLine(num);
        }
    }

}